/* Clasa abstracta pentru realizarea de subclase in care se aplica
   algoritmul backtracking.
   Programatorul care creeaza subclasele trebuie sa defineasca un
   constructor (care initializeaza stiva) si sa defineasca metodele
   succesor(), esteValid(succesor) si solutie()
*/

import java.util.*;

public abstract class Backtracking {
  /* Se foloseste drept stiva o lista, la care operatiile
     se fac numai la capatul din dreapta
  */
  protected ArrayList stiva; 

  protected Backtracking() {
    stiva=new ArrayList();
  }

  /* Itereaza succesorii valizi, pana cand stiva contine o solutie, pe
     care o intoarce. Daca stiva se goleste, intoarce null
  */
  public Object solutiaUrmatoare() {
    Object succesorValid;
    if(stiva.isEmpty()) return null;
    ElemStiva varfStiva=(ElemStiva)stiva.get(stiva.size()-1);
    Object solutie=null;
    do {
      succesorValid=succesorValid();
      if(succesorValid!=null) solutie=solutie();
    } while(succesorValid!=null && solutie==null);
    return solutie;
  }

  /* Cauta urmatorul succesor valid al elementului din varful stivei 
     si il intoarce. Daca un astfel de succesor nu exista, se elimina
     elementul din varful stivei si se continua cautarea cu elementul
     precedent. Daca stiva se goleste, intoarce null;
  */
  protected Object succesorValid() {
    Object succesor=null;
    boolean gasitSuccesorValid=false;
    while(!stiva.isEmpty() && !gasitSuccesorValid) {
      succesor=succesor();
      if(succesor!=null) {
        /* S-a gasit un succesor si se verifica daca este valid */
        if(esteValid(succesor)) {
            /* S-a gasit un succesor valid, care este pus in stiva */
            ElemStiva elementNou=new ElemStiva(succesor);
            stiva.add(elementNou); // punere in stiva
            gasitSuccesorValid=true;
        }
        else {
          /* Daca succesorul nu este valid, se memoreaza acesta
             ca ultim succesor vizitat al elementului din varful
             stivei si se continua cautarea
          */
          ElemStiva varfStiva=(ElemStiva)stiva.get(stiva.size()-1);
          varfStiva.ultimSuccesorVizitat=succesor;
        }
      }
      else {
        /* Varful curent al stivei nu mai are succesori, deci se
           elimina din stiva
        */ 
        ElemStiva varfStiva=(ElemStiva)stiva.remove(stiva.size()-1);
          // s-a scos din stiva
        if(!stiva.isEmpty()) {
          /* Daca stiva nu este vida, se continua cautarea pentru
             noul varf al stivei
          */
          ElemStiva varfNou=(ElemStiva)stiva.get(stiva.size()-1);
          varfNou.ultimSuccesorVizitat=varfStiva.element;
        }
      }
    }
    return succesor;
  }

  /* Verifica daca stiva contine o solutie; in caz afirmativ 
     construieste si intoarce aceasta solutie, altfel intoarce null
  */
  protected abstract Object solutie();

  /* Determina un succesor elementului din varful stivei, care urmeaza
     dupa ultimul succesor parcurs al acestui element; intoarce 
     succesorul obtinut sau, daca nu exista, intoarce null
  */
  protected abstract Object succesor();

  /* Verifica daca succesorul este valid, luand in consideratie 
     continutul stivei
  */
  protected abstract boolean esteValid(Object succesor);

  /* Clasa interioara pentru elementele de stiva */
  protected class ElemStiva {
    Object element;
    Object ultimSuccesorVizitat;

    public ElemStiva(Object element) {
      this.element=element; // informatia continuta
      ultimSuccesorVizitat=null;
    }

    /* Doua elemente de stiva sunt considerate egale, daca contin
       aceeasi informatie
    */
    public boolean equals(Object obj) {
      return this.element.equals(obj);
    }

    public String toString() {
      return "("+element+" "+ultimSuccesorVizitat+")";
    }
  }
}
